package 力扣._23_合并K个升序链表;

import 力扣.公用数据结构.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution2 {


    public ListNode mergeKLists(ListNode[] lists) {
        //优先队列——堆
        ListNode h = new ListNode();
        ListNode r = h;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
        //先进入一轮
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                queue.add(lists[i]);
                lists[i] = lists[i].next;
            }
        }
        while (!queue.isEmpty()) {
            ListNode min = queue.remove();     //取最小
            r.next = min;      //插入
            r = min;

            if (min.next != null)
                queue.add(min.next);
        }
        return h.next;
    }

    public static void main(String[] args) {
        ListNode[] lists = new ListNode[3];
        ListNode listNode = new Solution2().mergeKLists(lists);
    }
}
